import java.util.*;
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }

    /**
     * 两数之和
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        //方法1
        // int n=nums.length;
        // int[] arr=new int[2];
        // for(int i=0;i<n;i++){
        //     for(int j=i+1;j<n;j++){
        //         if(nums[i]+nums[j]==target){
        //             arr[0]=i;
        //             arr[1]=j;
        //             break;
        //         }
        //     }
        // }
        // return arr;
        //方法2
        Map<Integer,Integer> hash=new HashMap<>();
        int n=nums.length;
        for(int i=0;i<n;i++){
            int x=target-nums[i];
            if(hash.containsKey(x)){
                return new int[]{i,hash.get(x)};
            }
            hash.put(nums[i],i);
        }
        return new int[]{-1,-1};
    }

    /**
     * 存在重复元素1
     * @param nums
     * @return
     */
    public static boolean containsDuplicate(int[] nums) {
        int n=nums.length;
        Set<Integer> hash=new HashSet<>();
        for(int i=0;i<n;i++){
            if(hash.contains(nums[i])){
                return true;
            }
            hash.add(nums[i]);
        }
        return false;
    }

    /**
     * 存在重复元素2
     * @param nums
     * @param k
     * @return
     */
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> hash=new HashMap<>();
        int n=nums.length;
        for(int i=0;i<n;i++){
            if(hash.containsKey(nums[i])){
                if(i-hash.get(nums[i])<=k){
                    return true;
                }
            }
            hash.put(nums[i],i);
        }
        return false;
    }
    /**
     * 数青蛙
     * @param croakOfFrogs
     * @return
     */
    public static int minNumberOfFrogs(String croakOfFrogs) {
        char[] str=croakOfFrogs.toCharArray();
        int n=str.length;
        String s="croak";
        int num=s.length();
        int[] hash=new int[num];
        Map<Character,Integer> hash1=new HashMap<>();
        for(int i=0;i<num;i++){
            hash1.put(s.charAt(i),i);
        }
        for(char ch:str){
            if(ch==s.charAt(0)){
                if(hash[num-1]!=0){
                    hash[num-1]--;
                }
                hash[0]++;
            }else{
                int i=hash1.get(ch);
                if(hash[i-1]==0){
                    return -1;
                }
                hash[i-1]--;
                hash[i]++;
            }
        }
        for(int i=0;i<num-1;i++){
            if(hash[i]!=0){
                return -1;
            }
        }
        return hash[num-1];
    }
}